package Leetcode第一期;

public class 最长公共前缀_14 {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String pre = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(pre) != 0) { //0表示存在匹配的字符串，-1则表示无
                pre = pre.substring(0, pre.length() - 1); //截取字符串 一个一个字符往前所缩减
                if (pre.isEmpty()) return "";
            }
        }
        return pre;
    }

    public static void main(String[] args) {
        String[] strs = new String[]{"aabb", "aabcb"};
        int res = strs[1].indexOf(strs[0]);
        System.out.println(res);
    }


    //分治方法：
    public String longestCommonPrefix1(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return longestCommonPrefix2(strs, 0, strs.length - 1);
    }

    private String longestCommonPrefix2(String[] strs, int L, int R) {
        if (L == R) {
            return strs[R];
        } else {
            int mid=(L+R)/2; //向上取整
            String left=longestCommonPrefix2(strs,L,mid);
            String right=longestCommonPrefix2(strs,mid+1,R);
            return commonPrefix(left,right);
        }
    }
    String commonPrefix(String left, String right) {
        int min=Math.min(left.length(),right.length());
        for (int i=0;i<min;i++){
            if (left.charAt(i)!=right.charAt(i)){
                return left.substring(0,i);
            }
        }
        return left.substring(0,min);
    }

}
